02 贝尔曼公式

记 $G_t$ 为某个轨迹的discounted return，则State Value（状态值）就是 $G_t$ 的期望值。

即

v_\pi(s) = E[G_t|S_t = s]

状态值基于策略，是关于state的函数。

\begin{align*} v_\pi(s) & = E[G_t|S_t = s] \\ & = E[R_{t + 1} + \gamma G_{t + 1} |S_t = s] \\ & = E[R_{t + 1}|S_t = s] + \gamma E[G_{t + 1}|S_t = s] \end{align*}

\begin{align*} E[R_{t + 1}|S_t = s] & = \mathop{\Sigma}\limits_{a}\pi(a|s)E[R_t + 1|S_t = s, A_t = a] \\ & = \mathop{\Sigma}\limits_{a}\pi(a|s)\mathop{\Sigma}\limits_{r}p(r|s, a)r \end{align*}

\begin{align*} E[G_{t + 1}|S_t = s] & = \mathop{\Sigma}\limits_{s\prime} E[G_{t + 1}|S_t = s, S_{t + 1} = s\prime]p(s\prime|s) \\ & = \mathop{\Sigma}\limits_{s\prime} E[G_{t + 1}|S_{t + 1} = s\prime]p(s\prime|s) \\ & = \mathop{\Sigma}\limits_{s\prime} v_\pi(s\prime)p(s\prime|s) \\ & = \mathop{\Sigma}\limits_{s\prime} v_\pi(s\prime)\mathop{\Sigma}\limits_{a}p(s\prime|s, a)\pi(a|s) \end{align*}

（上式第二个等号源于马尔可夫性质）

由于 $v_\pi(s\prime)$ 与 $a$ 无关

\begin{align*} E[G_{t + 1}|S_t = s] & = \mathop{\Sigma}\limits_{s\prime} v_\pi(s\prime)\mathop{\Sigma}\limits_{a}p(s\prime|s, a)\pi(a|s) \\ & = \mathop{\Sigma}\limits_{s\prime}\mathop{\Sigma}\limits_{a}v_\pi(s\prime)p(s\prime|s, a)\pi(a|s) \\ & = \mathop{\Sigma}\limits_{a}\mathop{\Sigma}\limits_{s\prime}v_\pi(s\prime)p(s\prime|s, a)\pi(a|s) \\ & = \mathop{\Sigma}\limits_{a}\pi(a|s)\mathop{\Sigma}\limits_{s\prime}v_\pi(s\prime)p(s\prime|s, a) \end{align*}

（上式也可以直接从定义推出）

\begin{align*} v_\pi(s) & = \mathop{\Sigma}\limits_{a}\pi(a|s)\mathop{\Sigma}\limits_{r}p(r|s, a)r + \mathop{\Sigma}\limits_{a}\pi(a|s)\mathop{\Sigma}\limits_{s\prime}v_\pi(s\prime)p(s\prime|s, a) \\ & = \mathop{\Sigma}\limits_{a}\pi(a|s)[\mathop{\Sigma}\limits_{r}p(r|s, a)r + \gamma\mathop{\Sigma}\limits_{s\prime}v_\pi(s\prime)p(s\prime|s, a)] \end{align*}

最后得到的

v_\pi(s) = \mathop{\Sigma}\limits_{a}\pi(a|s)[\mathop{\Sigma}\limits_{r}p(r|s, a)r + \gamma\mathop{\Sigma}\limits_{s\prime}v_\pi(s\prime)p(s\prime|s, a)]

即为贝尔曼公式。

贝尔曼公式描述了不同状态值之间的关系。对于某个策略、状态等，贝尔曼公式实际是一组式子，联立可以求出各个状态量的具体值。

将贝尔曼公式写作

v_\pi(s) = r_\pi(s) + \gamma \mathop{\Sigma}\limits_{s\prime}p_\pi(s\prime|s)v_\pi(s\prime)

其中 $r_\pi(s)$ 是在现有策略下从 $s$ 出发立刻得到的平均奖励， $p_\pi(s\prime|s)$ 是从 $s$ 到 $s\prime$ 的概率。

将 $s_i$ 从 $1$ 到 $i$ 编号，则上式写为

v_\pi(s_i) = r_\pi(s_i) + \gamma \mathop{\Sigma}\limits_{s\prime}p_\pi(s_j|s_i)v_\pi(s_j)

将所有式子排列在一起，即可写为矩阵形式

v_\pi = r_\pi + \gamma P_\pi v_\pi

其中

最简单（但复杂度高）的求解方式是求逆。

v_\pi = (I - \gamma P_\pi)^{-1}r_\pi

另一种方式是迭代。可以假设其中某个 $v_i$ 是任一一个值，将其带入求 $v_{i + 1}$ ，不断迭代，当迭代次数趋于无穷时，对应的状态值趋于真实值。

action value（动作价值）指在某个状态下采取某个行动，能得到的平均回报。action value用于衡量在某个状态下，哪个动作的价值更高。

即有

q_\pi(s, a) = E[G_t|S_t = s, A_t = a]

v_\pi(s) = \mathop{\Sigma}\limits_{a}\pi(a|s)q_\pi(s,a)

和贝尔曼公式联立，有

q_\pi(s,a) = \mathop{\Sigma}\limits_{r}p(r|s, a)r + \gamma \mathop{\Sigma}\limits_{s\prime}p(s\prime|s,a)v_\pi(s\prime)

这个式子说明状态价值和动作价值可以相互转化。

02 贝尔曼公式​